package cxydmmszl.chapter09.t162.middle;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * <li style="color: red;">Prob</li>
 * 正数数组的最小不可组成和（进阶）
 * <li style="color: green;">Desc</li>
 * 给定一个正数数组 arr，其中所有的值都为整数，以下是最小不可组成和的概念：<br/>
 * 把 arr 每个子集内的所有元素加起来会出现很多值，其中最小的记为 min，最大的记为 max。<br/>
 * 在区间 [min,max] 上，如果有数不可以被 arr 某一个子集相加得到，
 * 那么其中最小的那个数是 arr 的最小不可组成和。<br/>
 * 在区间 [min,max] 上，如果所有的数都可以被 arr 的某一个子集相加得到，
 * 那么 max+1 是 arr 的最小不可组成和。<br/>
 * 请写函数返回正数数组arr的最小不可组成和。<b>保证 1 一定出现过！</b><br/>
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 1⩽arr[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N，表示数组长度。
 * 接下来一行 N 个整数表示数组内的元素。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示数组的最小不可组成和。
 * <li style="color: blue;">Link</li> CD69
 *
 * @author habitplus
 * @since 2021-10-16 17:26
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (Exception e) {
            throw new RuntimeException("input is invalid!");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        long ans = minUnformedSum(arr);
        System.out.println(ans);
    }

    private static long minUnformedSum(int[] arr) {
        if (arr == null || arr.length == 0) return 1;
        /*
            思路：排序
            range 代表当计算到 arr[i] 时，[1,range] 区间内所有的正数都能被 arr[0,i-1]的某个子集加出来；
            arr[0] = 1, range = 0;
         */
        Arrays.sort(arr);

        long range = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i] > range + 1) {
                // 因为 arr 有序，所以后面更加不可能会出现组成 range + 1
                // 直接返回 range + 1
                return range + 1;
            } else {
                // arr[i] <= range + 1
                // [1, range+1] 中的每一个数一定能由 arr[0, i] 上某个子集加出来
                range += arr[i];
            }
        }
        return range + 1;
    }
}
